#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // vector<int> nextGreaterElements(vector<int> &nums)
    // {
    //     int length = nums.size();
    //     vector<int> double_num = nums;
    //     for (auto num : nums)
    //     {
    //         double_num.push_back(num);
    //     }
    //     stack<int> stk;
    //     stk.push(0);
    //     vector<int> all_result(2 * length, -1);
    //     for (int i = 1; i < 2 * length; i++)
    //     {
    //         while (!stk.empty() && double_num[i] > double_num[stk.top()])
    //         {
    //             all_result[stk.top()] = double_num[i];
    //             stk.pop();
    //         }
    //         stk.push(i);
    //     }
    //     return vector<int>{all_result.begin(), all_result.begin() + length};
    // }

    vector<int> nextGreaterElements(vector<int> &nums)
    {
        int length=nums.size();
        stack<int> stk;
        stk.push(0);
        vector<int> res(length,-1);
        for(int i=1;i<2*length;i++)
        {
            while(!stk.empty()&&nums[i%length]>nums[stk.top()])
            {
                res[stk.top()]=nums[i%length];
                stk.pop();
            }
            stk.push(i%length);
        }
        return res;
    }
};

int main()
{
    vector<int> nums{1, 2, 1};
    Solution sol;
    vector<int> res = sol.nextGreaterElements(nums);
    for (auto num : res)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}